home *** CD-ROM | disk | FTP | other *** search
/ Personal Computer World 2005 October / PCWOCT05.iso / Software / FromTheMag / XAMPP 1.4.14 / xampp-win32-1.4.14-installer.exe / xampp / php / pear / Structures / Graph / Node.php
PHP Script  |  2004-10-01  |  11KB  |  340 lines
  1. <?php
  2. /* vim: set expandtab tabstop=4 shiftwidth=4 foldmethod=marker: */
  3. // +-----------------------------------------------------------------------------+
  4. // | Copyright (c) 2003 SΘrgio Gonτalves Carvalho                                |
  5. // +-----------------------------------------------------------------------------+
  6. // | This file is part of Structures_Graph.                                      |
  7. // |                                                                             |
  8. // | Structures_Graph is free software; you can redistribute it and/or modify    |
  9. // | it under the terms of the GNU Lesser General Public License as published by |
  10. // | the Free Software Foundation; either version 2.1 of the License, or         |
  11. // | (at your option) any later version.                                         |
  12. // |                                                                             |
  13. // | Structures_Graph is distributed in the hope that it will be useful,         |
  14. // | but WITHOUT ANY WARRANTY; without even the implied warranty of              |
  15. // | MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the               |
  16. // | GNU Lesser General Public License for more details.                         |
  17. // |                                                                             |
  18. // | You should have received a copy of the GNU Lesser General Public License    |
  19. // | along with Structures_Graph; if not, write to the Free Software             |
  20. // | Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA                    |
  21. // | 02111-1307 USA                                                              |
  22. // +-----------------------------------------------------------------------------+
  23. // | Author: SΘrgio Carvalho <sergio.carvalho@portugalmail.com>                  |
  24. // +-----------------------------------------------------------------------------+
  25. //
  26. /**
  27.  * This file contains the definition of the Structures_Graph_Node class
  28.  * 
  29.  * @see Structures_Graph_Node
  30.  * @package Structures_Graph
  31.  */
  32.  
  33. /* dependencies {{{ */
  34. /** */
  35. require_once 'PEAR.php';
  36. /** */
  37. require_once 'Structures/Graph.php';
  38. /* }}} */
  39.  
  40. /* class Structures_Graph_Node {{{ */
  41. /**
  42.  * The Structures_Graph_Node class represents a Node that can be member of a 
  43.  * graph node set.
  44.  *
  45.  * A graph node can contain data. Under this API, the node contains default data, 
  46.  * and key index data. It behaves, thus, both as a regular data node, and as a 
  47.  * dictionary (or associative array) node.
  48.  * 
  49.  * Regular data is accessed via getData and setData. Key indexed data is accessed
  50.  * via getMetadata and setMetadata.
  51.  *
  52.  * @author        SΘrgio Carvalho <sergio.carvalho@portugalmail.com> 
  53.  * @copyright    (c) 2004 by SΘrgio Carvalho
  54.  * @package Structures_Graph
  55.  */
  56. /* }}} */
  57. class Structures_Graph_Node {
  58.     /* fields {{{ */
  59.     /** 
  60.      * @access private 
  61.      */
  62.     var $_data = null;
  63.     /** @access private */
  64.     var $_metadata = array();
  65.     /** @access private */
  66.     var $_arcs = array();
  67.     /** @access private */
  68.     var $_graph = null;
  69.     /* }}} */
  70.  
  71.     /* Constructor {{{ */
  72.     /**
  73.     *
  74.     * Constructor
  75.     *
  76.     * @access    public
  77.     */
  78.     function Structures_Graph_Node() {
  79.     }
  80.     /* }}} */
  81.  
  82.     /* getGraph {{{ */
  83.     /**
  84.     *
  85.     * Node graph getter
  86.     *
  87.     * @return    Structures_Graph    Graph where node is stored
  88.     * @access    public
  89.     */
  90.     function &getGraph() {
  91.         return $this->_graph;
  92.     }
  93.     /* }}} */
  94.  
  95.     /* setGraph {{{ */
  96.     /**
  97.     *
  98.     * Node graph setter. This method should not be called directly. Use Graph::addNode instead.
  99.     *
  100.     * @param    Structures_Graph   Set the graph for this node. 
  101.     * @see      Structures_Graph::addNode()
  102.     * @access    public
  103.     */
  104.     function setGraph(&$graph) {
  105.         $this->_graph =& $graph;
  106.     }
  107.     /* }}} */
  108.  
  109.     /* getData {{{ */
  110.     /**
  111.     *
  112.     * Node data getter.
  113.     * 
  114.     * Each graph node can contain a reference to one variable. This is the getter for that reference.
  115.     *
  116.     * @return    mixed    Data stored in node
  117.     * @access    public
  118.     */
  119.     function &getData() {
  120.         return $this->_data;
  121.     }
  122.     /* }}} */
  123.  
  124.     /* setData {{{ */
  125.     /**
  126.     *
  127.     * Node data setter
  128.     *
  129.     * Each graph node can contain a reference to one variable. This is the setter for that reference.
  130.     *
  131.     * @return    mixed    Data to store in node
  132.     * @access    public
  133.     */
  134.     function setData($data) {
  135.         $this->_data =& $data;
  136.     }
  137.     /* }}} */
  138.  
  139.     /* metadataKeyExists {{{ */
  140.     /**
  141.     *
  142.     * Test for existence of metadata under a given key.
  143.     *
  144.     * Each graph node can contain multiple 'metadata' entries, each stored under a different key, as in an 
  145.     * associative array or in a dictionary. This method tests whether a given metadata key exists for this node.
  146.     *
  147.     * @param    string    Key to test
  148.     * @return    boolean     
  149.     * @access    public
  150.     */
  151.     function metadataKeyExists($key) {
  152.         return array_key_exists($key, $this->_metadata);
  153.     }
  154.     /* }}} */
  155.  
  156.     /* getMetadata {{{ */
  157.     /**
  158.     *
  159.     * Node metadata getter
  160.     *
  161.     * Each graph node can contain multiple 'metadata' entries, each stored under a different key, as in an 
  162.     * associative array or in a dictionary. This method gets the data under the given key. If the key does
  163.     * not exist, an error will be thrown, so testing using metadataKeyExists might be needed.
  164.     *
  165.     * @param    string  Key
  166.     * @param    boolean nullIfNonexistent (defaults to false).
  167.     * @return    mixed    Metadata Data stored in node under given key
  168.     * @see      metadataKeyExists
  169.     * @access    public
  170.     */
  171.     function &getMetadata($key, $nullIfNonexistent = false) {
  172.         if (array_key_exists($key, $this->_metadata)) {
  173.             return $this->_metadata[$key];
  174.         } else {
  175.             if ($nullIfNonexistent) {
  176.                 return null;
  177.             } else {
  178.                 Pear::raiseError('Structures_Graph_Node::getMetadata: Requested key does not exist', STRUCTURES_GRAPH_ERROR_GENERIC);
  179.             }
  180.         }
  181.     }
  182.     /* }}} */
  183.  
  184.     /* unsetMetadata {{{ */
  185.     /**
  186.     *
  187.     * Delete metadata by key
  188.     *
  189.     * Each graph node can contain multiple 'metadata' entries, each stored under a different key, as in an 
  190.     * associative array or in a dictionary. This method removes any data that might be stored under the provided key.
  191.     * If the key does not exist, no error is thrown, so it is safe using this method without testing for key existence.
  192.     *
  193.     * @param    string  Key
  194.     * @access    public
  195.     */
  196.     function unsetMetadata($key) {
  197.         if (array_key_exists($key, $this->_metadata)) unset($this->_metadata[$key]);
  198.     }
  199.     /* }}} */
  200.  
  201.     /* setMetadata {{{ */
  202.     /**
  203.     *
  204.     * Node metadata setter
  205.     *
  206.     * Each graph node can contain multiple 'metadata' entries, each stored under a different key, as in an 
  207.     * associative array or in a dictionary. This method stores data under the given key. If the key already exists,
  208.     * previously stored data is discarded.
  209.     *
  210.     * @param    string  Key
  211.     * @param    mixed   Data 
  212.     * @access    public
  213.     */
  214.     function setMetadata($key, $data) {
  215.         $this->_metadata[$key] =& $data;
  216.     }
  217.     /* }}} */
  218.  
  219.     /* _connectTo {{{ */
  220.     /** @access private */
  221.     function _connectTo(&$destinationNode) {
  222.         $this->_arcs[] =& $destinationNode;
  223.     }
  224.     /* }}} */
  225.  
  226.     /* connectTo {{{ */
  227.     /**
  228.     *
  229.     * Connect this node to another one.
  230.     * 
  231.     * If the graph is not directed, the reverse arc, connecting $destinationNode to $this is also created.
  232.     *
  233.     * @param    Structures_Graph Node to connect to
  234.     * @access    public
  235.     */
  236.     function connectTo(&$destinationNode) {
  237.         // We only connect to nodes
  238.         if (!is_a($destinationNode, 'Structures_Graph_Node')) 
  239.             Pear::raiseError('Structures_Graph_Node::connectTo received an object that is not a Structures_Graph_Node', STRUCTURES_GRAPH_ERROR_GENERIC);
  240.         // Nodes must already be in graphs to be connected
  241.         if ($this->_graph == null)
  242.             Pear::raiseError('Structures_Graph_Node::connectTo Tried to connect a node that is not in a graph', STRUCTURES_GRAPH_ERROR_GENERIC);
  243.         if ($destinationNode->getGraph() == null) 
  244.             Pear::raiseError('Structures_Graph_Node::connectTo Tried to connect to a node that is not in a graph', STRUCTURES_GRAPH_ERROR_GENERIC);
  245.         // Connect here
  246.         $this->_connectTo($destinationNode);
  247.         // If graph is undirected, connect back
  248.         if (!$this->_graph->isDirected()) {
  249.             $destinationNode->_connectTo($this);
  250.         }
  251.     }
  252.     /* }}} */
  253.  
  254.     /* getNeighbours {{{ */
  255.     /**
  256.     *
  257.     * Return nodes connected to this one.
  258.     * 
  259.     * @return   array   Array of nodes
  260.     * @access    public
  261.     */
  262.     function getNeighbours() {
  263.         return $this->_arcs;
  264.     }
  265.     /* }}} */
  266.  
  267.     /* connectsTo {{{ */
  268.     /**
  269.     *
  270.     * Test wether this node has an arc to the target node
  271.     *
  272.     * @return    boolean   True if the two nodes are connected
  273.     * @access    public
  274.     */
  275.     function connectsTo(&$target) {
  276.         $copy = $target;
  277.         $arcKeys = array_keys($this->_arcs);
  278.         foreach($arcKeys as $key) {
  279.             /* ZE1 chokes on this expression:
  280.                 if ($target === $arc) return true;
  281.               so, we'll use more convoluted stuff
  282.             */
  283.             $arc =& $this->_arcs[$key];
  284.             $target = true;
  285.             if ($arc === true) {
  286.                 $target = false;
  287.                 if ($arc === false) {
  288.                     $target = $copy;
  289.                     return true;
  290.                 }
  291.             }
  292.         }
  293.         $target = $copy;
  294.         return false;
  295.     }
  296.     /* }}} */
  297.  
  298.     /* inDegree {{{ */
  299.     /**
  300.     *
  301.     * Calculate the in degree of the node.
  302.     * 
  303.     * The indegree for a node is the number of arcs entering the node. For non directed graphs, 
  304.     * the indegree is equal to the outdegree.
  305.     *
  306.     * @return    integer     In degree of the node
  307.     * @access    public
  308.     */
  309.     function inDegree() {
  310.         if ($this->_graph == null) return 0;
  311.         if (!$this->_graph->isDirected()) return $this->outDegree();
  312.         $result = 0;
  313.         $graphNodes =& $this->_graph->getNodes();
  314.         foreach (array_keys($graphNodes) as $key) {
  315.             if ($graphNodes[$key]->connectsTo($this)) $result++;
  316.         }
  317.         return $result;
  318.         
  319.     }
  320.     /* }}} */
  321.  
  322.     /* outDegree {{{ */
  323.     /**
  324.     *
  325.     * Calculate the out degree of the node.
  326.     *
  327.     * The outdegree for a node is the number of arcs exiting the node. For non directed graphs,
  328.     * the outdegree is always equal to the indegree.
  329.     * 
  330.     * @return    integer     Out degree of the node
  331.     * @access    public
  332.     */
  333.     function outDegree() {
  334.         if ($this->_graph == null) return 0;
  335.         return sizeof($this->_arcs);
  336.     }
  337.     /* }}} */
  338. }
  339. ?>
  340.